class Solution(object):
    def countPalindromicSubsequence(self, s):
        first = {}
        latest = {}
        for index, c in enumerate(s):
            if c not in first:
                first[c] = index
            latest[c] = index
        ans = 0
        for key in first:
            if latest[key] - first[key] > 1:
                mid_c = set()
                for i in range(first[key] + 1, latest[key]):
                    mid_c.add(s[i])
                ans += len(mid_c)
        return ans